#include <iostream>
#include <vector>
#include <algorithm> // 用于max
using namespace std;

// 求子数组 a[left..right] 的最大子数组和
int maxSum(const vector<int>& a, int left, int right) {
    if (left == right) return a[left]; // 仅一个元素时直接返回

    // 第1步：划分
    int mid = left + (right - left) / 2;

    // 第2步：求解子问题
    int s1 = maxSum(a, left, mid);      // 递归求左子数组
    int s2 = maxSum(a, mid + 1, right); // 递归求右子数组

    // 求中间段的和
    int maxleft = 0, maxright = 0, ls = 0, rs = 0;
    for (int i = mid; i >= left; i--) 
        maxleft = max(maxleft, ls += a[i]);
    for (int j = mid + 1; j <= right; j++) 
        maxright = max(maxright, rs += a[j]);

    // 第3步：合并解并返回
    int max_s = max(s1, s2);
    if (maxleft + maxright > 0) 
        max_s = max(max_s, maxleft + maxright);

    return max_s;
}

int main() {
    vector<int> a = {-20, 10, -30, 40, -10, 20, 10, -50, 40};
    int sum = maxSum(a, 0, a.size() - 1);
    cout << "最大子数组和为：" << sum << endl;
    return 0;
}